In a traditional cellular network, mobile units establish direct downlink and uplink connections with a backbone network access point such as a cellular base station (BTS). A recently proposed hybrid-cellular network (HCN) seeks to alleviate the limitations of traditional cellular systems by allowing uplink and downlink connections to involve more than one link, with all links either originating, or terminating at the BTS. Such a system is a hybrid between cellular and ad hoc network architectures, where uplink and/or downlink data is relayed to and from the BTS by other mobile units or dedicated repeaters. An example of HCN 100 is depicted in FIG. 1. As is evident, communication to/from base station 102 may exist either as a direct link to the mobile unit (as with mobile unit 101) or may have one or more intermediate relays (as with mobile unit 104 being routed through mobile unit 103). With the introduction of intermediate relays, long-range transmission can be broken into several shorter-range links, allowing for a reduction in the BTS transmission power on the downlink and increasing capacity of the uplink.
A major challenge in constructing a hybrid-cellular network is implementing an efficient routing protocol. The process of routing in a network from a node A1 to a node A2 consists of establishing a sequence of intermediate nodes that are used as relays to transmit information from node A1 to node A2, and from node A2 to node A1. Routing can be direct when no intermediate node is involved from transmitting from node A1 to node A2, and from node A2 to node A1. The goal is to create a robust routing protocol capable of maintaining routing information in a highly mobile network, yet without the overhead of excessive signaling. Most of the research activities on this subject have focused on adapting ad hoc routing protocols, such as Ad hoc On-demand Vector Routing (AODV), Dynamic Source Routing (DSR), and Destination-Sequenced Distance Vector Routing, for use in an HCN. These protocols are efficient for gathering and maintaining routing information in a general ad hoc network, involving topology with multiple source-destination pairs, but are needlessly complicated for an HCN topology, where every route has a common source or destination node. Therefore, a need exists for a routing protocol within a HCN that is less complicated for HCN topologies, yet is efficient for gathering and maintaining routing information.